In Internet communications, electronic packets of data are sent from an originating host to a receiving host by means of the Internet Protocol (IP). IP uses routers to transmit packets from hosts connected to one IP sub-network, or subnet, to hosts connected to different IP sub-networks. When an IP host (the source host) transmits a packet to another IP host (the destination), the source host consults a routing table to determine the IP address of the router that should be used to forward the packet to the destination host.
This IP address lookup is a major bottleneck in high performance routers. The current Internet Protocol, IPv6, specifies a 128-bit IP destination address. In IPv6, the 128-bit address is represented as a series of bytes separated by “:”. Further, sets of contiguous zeros can be represented as “::”. Address lookup would be simple if each 128-bit IP destination address could be looked up in a table that lists the output link for every assigned Internet address. In such a case, a hashing algorithm could be used for address lookup, but a router would have to keep millions or even billions of trie node blocks. To reduce database size, and the traffic needed to continually update the databases, a router database actually consists of a smaller set of address prefixes. This reduces router database size, but at the cost of requiring a more complex lookup scheme called longest matching prefix.
The longest matching prefix address lookup scheme requires the router to determine which of the prefixes in the router database has the longest exact match when compared to the destination address in the packet. For example, a router database may have the address prefixes P1=0101, P2=0101101, and P3=010110101011. If the first 12 bits of the destination address are 010110101101, the longest matching prefix is P2. But, if the first 12 bits of the destination address are 010110101011, the longest matching prefix is P3.
A number of trie-based techniques (i.e., techniques using trie node blocks to organize pre-fixes within the routing database) have been developed for conducting this longest matching prefix address lookup. The most commonly available address lookup implementation is a radix trie implementation. The radix trie implementation may require up to 128 memory accesses for an address lookup. Although, with binary branching, an implementation having 40,000 address prefixes may only require 16 memory accesses. An extension of the radix trie algorithm, dynamic prefix tries, may also require up to 128 memory accesses for address lookup. The Lulea scheme uses a three-level tree structure for the routing table. This scheme is essentially a three-level fixed-stride trie in which the trie nodes are compressed using a bitmap. Using this structure, a 32-bit address requires at most 12 memory accesses.
One of the more flexible and effective address lookup techniques is controlled prefix expansion. In this technique, tries of a predetermined height (e.g., 8-bits) (and hence with a predetermined number of memory accesses per lookup) are constructed for a prefix set. Dynamic programming algorithms are used to obtain space optimal fixed-stride and variable-stride tries of a given height.